package com.wc.data_structures.tree;


import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @Author congge
 * @Date 2023/4/22 16:06
 * @description
 */
public class BinaryTree<T> {
    public TreeNode<T> root;

    public BinaryTree() {

    }

    public BinaryTree(TreeNode<T> root) {
        this.root = root;
    }

    /**
     * 先序遍历
     * @return 先续遍历数组
     */
    public List<T> preOrder() {
        return preOrder(root);
    }

    /**
     * 中序遍历
     * @return 中续遍历数组
     */
    public List<T> inOrder() {
        return inOrder(root);
    }

    /**
     * 后续遍历
     * @return 后续遍历数组
     */
    public List<T> postOrder() {
        return postOrder(root);
    }

    public List<List<T>> levelOrder() {
        return levelOrder(root);
    }

    /**
     * 先序遍历
     *
     * @param root 根
     */
    public List<T> preOrder(TreeNode<T> root) {
        if (root == null) {
            return null;
        }
        List<T> preOrderList = new ArrayList<>();
        preOrder(root, preOrderList);
        return preOrderList;
    }

    /**
     * 先序遍历
     *
     * @param root         树根
     * @param preOrderList 存放遍历
     */
    public void preOrder(TreeNode<T> root, List<T> preOrderList) {
        if (root == null) {
            return;
        }
        preOrderList.add(root.value);
        preOrder(root.left, preOrderList);
        preOrder(root.right, preOrderList);
    }

    /**
     * 中序遍历
     *
     * @param root 根
     */
    public List<T> inOrder(TreeNode<T> root) {
        if (root == null) {
            return null;
        }
        List<T> inOrderList = new ArrayList<>();
        inOrder(root, inOrderList);
        return inOrderList;
    }

    /**
     * 中序遍历
     *
     * @param root        树根
     * @param inOrderList 存放遍历
     */
    public void inOrder(TreeNode<T> root, List<T> inOrderList) {
        if (root == null) {
            return;
        }
        preOrder(root.left, inOrderList);
        inOrderList.add(root.value);
        preOrder(root.right, inOrderList);
    }

    /**
     * 中序遍历
     *
     * @param root 根
     */
    public List<T> postOrder(TreeNode<T> root) {
        if (root == null) {
            return null;
        }
        List<T> postOrderList = new ArrayList<>();
        postOrder(root, postOrderList);
        return postOrderList;
    }

    /**
     * 中序遍历
     *
     * @param root          树根
     * @param postOrderList 存放遍历
     */
    public void postOrder(TreeNode<T> root, List<T> postOrderList) {
        if (root == null) {
            return;
        }
        preOrder(root.left, postOrderList);
        preOrder(root.right, postOrderList);
        postOrderList.add(root.value);
    }

    /**
     * 层次遍历
     *
     * @param root 树根
     */
    public List<List<T>> levelOrder(TreeNode<T> root) {
        if (root == null) {
            return null;
        }
        List<List<T>> floorOrderList = new ArrayList<>();
        levelOrder(root, floorOrderList, 0);
        return floorOrderList;
    }

    /**
     * 层次遍历
     *
     * @param root           树根
     * @param floorOrderList 存放楼层的东西
     * @param floor          当前楼层
     */
    public void levelOrder(TreeNode<T> root, List<List<T>> floorOrderList, int floor) {
        if (root == null) {
            return;
        }
        List<T> floorTreeNode;
        if (floor == floorOrderList.size()) {
            floorTreeNode = new ArrayList<>();
            floorOrderList.add(floorTreeNode);
        } else {
            floorTreeNode = floorOrderList.get(floor);
        }
        floorTreeNode.add(root.value);
        levelOrder(root.left, floorOrderList, floor + 1);
        levelOrder(root.right, floorOrderList, floor + 1);
    }

    /**
     * 先序遍历查找
     *
     * @param root  树根
     * @param value 代查数组
     * @return
     */
    public TreeNode<T> preOrderSearch(TreeNode<T> root, T value) {
        if (root == null) {
            return null;
        }
        if (root.value.equals(value)) {
            return root;
        }
        TreeNode<T> ans = preOrderSearch(root.left, value);
        if (ans != null) {
            return ans;
        }
        ans = preOrderSearch(root.right, value);
        return ans;
    }

    /**
     * 中序遍历查找
     */
    public TreeNode<T> inOrderSearch(TreeNode<T> root, T value) {
        if (root == null) {
            return null;
        }
        TreeNode<T> ans = inOrderSearch(root.left, value);
        if (ans != null) {
            return ans;
        }
        if (root.value.equals(value)) {
            return root;
        }
        ans = inOrderSearch(root.right, value);
        return ans;
    }

    /**
     * 后序遍历查找
     */
    public TreeNode<T> postOrderSearch(TreeNode<T> root, T value) {
        if (root == null) {
            return null;
        }
        TreeNode<T> ans = postOrderSearch(root.left, value);
        if (ans != null) {
            return ans;
        }

        ans = postOrderSearch(root.right, value);
        if (ans != null) {
            return ans;
        }

        if (root.value.equals(value)) {
            return root;
        }

        return null;
    }

    /**
     * 删除节点
     */
    public TreeNode<T> deleteTree(T value) {
        if (root == null) {
            return null;
        }
        if (root.value == value) {
            TreeNode<T> oldNode = root;
            root = null;
            return oldNode;
        }
        return deleteTree(root, value);
    }

    /**
     * 删除root树中value值等于value的节点
     */
    public TreeNode<T> deleteTree(TreeNode<T> root, T value) {
        // 节点不存在返回
        if (root == null) {
            return null;
        }

        TreeNode<T> ans = null;
        // 查其左节点是否是
        if (root.left != null) {
            if (root.left.value == value) {
                ans = root.left;
                root.left = null;
            }
        }
        if (ans != null) {
            return ans;
        }
        // 查右面节点是否是
        if (root.right != null) {
            if (root.right.value == value) {
                ans = root.right;
                root.right = null;
            }
        }

        if (ans != null) {
            return ans;
        }

        // 查其左节点的左右节点
        ans = deleteTree(root.left, value);
        if (ans != null) {
            return ans;
        }
        // 查其右节点的左右节点
        ans = deleteTree(root.right, value);
        return ans;
    }

    public static void main(String[] args) {
        /*
         * 是先序建立节点
         * BinaryTreeUitl<String> binaryTreeUitl = new BinaryTreeUitl<>();
         *         TreeNode<String> root = binaryTreeUitl.preCreate();
         *         List<List<String>> levelOrder = binaryTreeUitl.levelOrder(root);
         *         for (List<String> level : levelOrder) {
         *             for (String num : level) {
         *                 System.out.print(num + "\t");
         *             }
         *             System.out.println();
         *         }
         */
    }

    public TreeNode<String> preCreate() {
        Scanner sc = new Scanner(System.in);
        TreeNode<String> root = new TreeNode<>();
        System.out.println("null 为 -1");
        System.out.print("根节点值：");
        root.value = sc.nextLine();
        preCreate(root, "null");
        return root;
    }


    public void preCreate(TreeNode<String> root, String nullNum) {
        Scanner sc = new Scanner(System.in);
        // 左子树的形状
        System.out.print("左节点值：");
        String num = sc.nextLine();
        root.left = new TreeNode<>();
        root.left.value = num;
        if (!num.equals(nullNum)) {
            preCreate(root.left, nullNum);
        }

        System.out.print("右节点值：");
        // 右子树
        num = sc.nextLine();
        root.right = new TreeNode<>();
        root.right.value = num;
        if (!num.equals(nullNum)) {
            preCreate(root.right, nullNum);
        }
    }


}




